/**************************************************************************************************
* Title: SumPointerTree.cpp
* Author: Gael Huber
* Description: A tree containing pointer information about free blocks of space. Pointers refer to
*	the starting address of the usable space within a block.
**************************************************************************************************/
#include "SumPointerTree.h"

/**************************************************************************************************
* Insert a node into the tree
**************************************************************************************************/
void PointerTree::insert(PointerTree::Node* node) {
	Node* y = 0;
	Node* x = root;

	// While the tree is still a valid node, continue to traverse
	while(x != 0) {
		y = x;
		if(node->getAddress() < x->getAddress()) {
			x = x->getLeft();
		} else {
			x = x->getRight();
		}
	};

	// The parent of the node we are inserting is set to the deepest valid node of our traversal
	node->setParent(y);

	// In the case of the tree being empty, set the node to insert as the root
	if(y == 0) {
		root = node;
	} else if (node->getAddress() < y->getAddress()) {
		y->setLeft(node);
	} else {
		y->setRight(node);
	}
}

/**************************************************************************************************
* Remove a node from the tree
**************************************************************************************************/
void PointerTree::remove(PointerTree::Node* node) {
	// If the node has no left child, its right child takes its place
	if(node->getLeft() == 0) {
		transplant(node, node->getRight());
	} else if(node->getRight() == 0) {
		// If it has a left child but no right child, the left child takes its place
		transplant(node, node->getLeft());
	} else {
		// Since both children exist, find the minimum node of the subtree to the right of the node
		Node* y = minimum(node->getRight());

		// If the parent of the minimum is not the node we are deleting
		if(y->getParent() != node) {
			// Transplant that node with its right child
			transplant(y, y->getRight());
			y->setRight(node->getRight());
			y->getRight()->setParent(y);
		}
		transplant(node, y);
		y->setLeft(node->getLeft());
		y->getLeft()->setParent(y);
	}
}
	
/**************************************************************************************************
* Check to see whether a node of a specified length exists
**************************************************************************************************/
const bool PointerTree::exists(MemAddress address) const {
	// Start at the root node
	Node* x = root;

	// While x is a valid node, keep searching for a match
	while(x != 0) {
		if(x->getAddress() == address) {
			// Exactly equal, we have a match
			return true;
		} else if(address < x->getAddress()) {
			// Head left
			x = x->getLeft();
		} else {
			// Head right
			x = x->getRight();
		}
	}

	// No matches were found, so that size must not exist
	return false;
}
	
/**************************************************************************************************
* Returns the first node of a specified length
**************************************************************************************************/
PointerTree::Node* const PointerTree::find(MemAddress address) const {
	// Start at the root node
	Node* x = root;

	// While x is a valid node, keep searching for a match
	while(x != 0) {
		if(x->getAddress() == address) {
			// Exactly equal, we have a match
			return x;
		} else if(address < x->getAddress()) {
			// Head left
			x = x->getLeft();
		} else {
			// Head right
			x = x->getRight();
		}
	}

	return 0;
}

/**************************************************************************************************
* Calculate and return the depth of the tree
**************************************************************************************************/
const UINT32 PointerTree::depth(void) const {
	UINT32 maxDepth = 0;	// Maximum depth starts at 0
	int depth = 0;		// Depth starts at 0

	// Start at the root
	Node* x = root;

	// Used for walking through the tree, permits us to know whether we should continue to go up or 
	// whether we should try to walk back down the tree.
	bool goUp = false;

	// Walk through the tree
	while(x != 0 && depth >= 0) {
		// If goUp is true, we have to try to rise back up through the tree, otherwise attempt to walk down the tree
		if(goUp == true) {
			// Check whether the parent node's right child is the current node (this means we have already
			// gone right, so we should keep going up). Also check that the parent node's right child is not
			// null. This also means we should continue going up. If neither of these conditions are true,
			// go to the new node.
			if(x->getParent()->getRight() == x) {
				// Keep going up!
				x = x->getParent();
				depth--;
			} else if(x->getParent()->getRight() == 0) {
				// Keep going up!
				x = x->getParent();
				depth--;
			} else {
				// Go to the right
				x = x->getParent()->getRight();
			}
		} else if(x->getLeft() != 0) {
			x = x->getLeft();
			depth++;
		} else if(x->getRight() != 0) {
			x = x->getRight();
			depth++;
		} else {
			// We have reached a leaf, so go up
			goUp = true;
		}

		// Check whether the depth needs to be updated
		if(depth > (int) maxDepth)
			maxDepth = depth;
	}

	return maxDepth;
}

/**************************************************************************************************
* Calculate and return the number of elements in the tree
**************************************************************************************************/
const UINT32 PointerTree::size(void) const {
	UINT32 size = 0;	// Size of the tree
	int depth = 0;		// Depth starts at 0, this is to ensure that we do not infinitely search the tree,
		// when depth is less than one we have been through the whole tree

	// Start at the root
	Node* x = root;

	// If root is valid, depth starts as 1
	if(x != 0)
		size = 1;

	// Used for walking through the tree, permits us to know whether we should continue to go up or 
	// whether we should try to walk back down the tree.
	bool goUp = false;

	// Walk through the tree
	while(x != 0 && depth >= 0) {
		// If goUp is true, we have to try to rise back up through the tree, otherwise attempt to walk down the tree
		if(goUp == true) {
			// Check whether the parent node's right child is the current node (this means we have already
			// gone right, so we should keep going up). Also check that the parent node's right child is not
			// null. This also means we should continue going up. If neither of these conditions are true,
			// go to the new node.
			if(x->getParent()->getRight() == x) {
				// Keep going up!
				x = x->getParent();
				depth--;
			} else if(x->getParent()->getRight() == 0) {
				// Keep going up!
				x = x->getParent();
				depth--;
			} else {
				// Go to the right
				x = x->getParent()->getRight();
				size++;
			}
		} else if(x->getLeft() != 0) {
			x = x->getLeft();
			depth++;
			size++;
		} else if(x->getRight() != 0) {
			x = x->getRight();
			depth++;
			size++;
		} else {
			// We have reached a leaf, so go up
			goUp = true;
		}
	}

	return size;
}

/**************************************************************************************************
* Calculate and return the number of elements in the tree
**************************************************************************************************/
void PointerTree::transplant(PointerTree::Node* u, PointerTree::Node* v) {
	// If u has no parent, then it must be the root node
	if(u->getParent() == 0) {
		root = v;
	} else if (u == u->getParent()->getLeft()) {
		// If u is the its parent's left child, v becomes that child now
		u->getParent()->setLeft(v);
	} else {
		// Otherwise, u must be its parent's right child
		u->getParent()->setRight(v);
	}

	// If v is not null, its new parent is u's parent
	if(v != 0)
		v->setParent(u->getParent());
}

/**************************************************************************************************
* Find the minimum node of the tree
**************************************************************************************************/
PointerTree::Node* const PointerTree::minimum(const PointerTree::Node* const node) const {
	Node* x = root;
	while(x->getLeft() != 0)
		x = x->getLeft();
	
	return x;
}

/**************************************************************************************************
* Find the maximum node of the tree
**************************************************************************************************/
PointerTree::Node* const PointerTree::maximum(const PointerTree::Node* const node) const {
	Node* x = root;
	while(x->getRight() != 0)
		x = x->getRight();
	
	return x;
}